﻿#define _CRT_SECURE_NO_WARNINGS 1
// 单调栈

// 下一个更大元素(1)
// 暴力解法:
/*
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {

        std::unordered_map<int, int> hashIndex;
        std::vector<int> v;

        // num2中的元素与自身对应的下标建立映射
        for (int i = 0; i < nums2.size(); ++i)
        {
            hashIndex[nums2[i]] = i;
        }

        for (int i = 0; i < nums1.size(); ++i)
        {
            // 因为num1是num2的子集,而且num2中的元素各不相同
            int maxNum = nums1[i]; // 用于比较且记录第一个大于nums1[i]的元素
            // 从该元素下一个位置开始遍历
            for (int j = hashIndex[nums1[i]] + 1; j < nums2.size(); ++j)
            {
                if (nums2[j] > maxNum)
                {
                    maxNum = nums2[j];
                    break;
                }
            }
            // 如果maxNum依旧等于num1[i]则插入-1,否则插入maxNum
            v.push_back(maxNum == nums1[i] ? -1 : maxNum);
        }

        return v;
    }
};
*/

// 单调栈解法:
/*
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {

        std::stack<int> st; // 单调栈
        std::vector<int> v(nums1.size(),-1);
        std::unordered_map<int,int> hashIndex;

        // 建立num1中的元素与其对应下标的关系
        for(int i=0;i<static_cast<int>(nums1.size());++i)
        {
            hashIndex[nums1[i]]=i;
        }

        // 因为是找右边第一个大于的元素,所以从右边开始遍历num2
        for(int end2=static_cast<int>(nums2.size()-1);end2>=0;--end2)
        {
            // 栈不为空,且当前num2[end2]元素大于top元素,则删除栈顶元素
            // 为什么是当前元素大于等于top元素就删除top元素呢?
            // 如果st3>st5
            // num2[end2]<st5 ---> num2[end2]<st3
            // 但st3没有存在的意义,因为是找右边第一个
            while(!st.empty() && st.top()<=nums2[end2])
            {
                st.pop();
            }

            // 如果该num2[end2]元素在num1中,则进行查找
            if(hashIndex.find(nums2[end2])!=hashIndex.end())
            {
                if(!st.empty()) // 栈不为空,就在该num2[end2]对应的位置插入查找的元素
                {
                    v[hashIndex[nums2[end2]]]=st.top();
                }
                else
                {
                    v[hashIndex[nums2[end2]]]=-1;
                }
            }

            st.push(nums2[end2]);
        }

        return v;
    }
*/

// 下一个更大元素(2,循环数组)
// 额外开辟了空间v[nums,nums]
/*
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {

        // 往v中尾插两边nums
        std::vector<int> v(nums.begin(),nums.end());
        v.insert(v.end(),nums.begin(),nums.end());

        std::stack<int> st; // 单调栈
        std::vector<int> ans(nums.size()); // 记录答案

        for(int end=static_cast<int>(v.size()-1);end>=0;--end)
        {
            while(!st.empty() && st.top()<=v[end])
            {
                st.pop();
            }

            if(end<static_cast<int>(nums.size()))
            {
                if(!st.empty())
                {
                    ans[end]=st.top();
                }
                else
                {
                    ans[end]=-1;
                }
            }

            st.push(v[end]);
        }

        return ans;
    }
};
*/

// mod运算
/*
  // 单调栈问题
    vector<int> nextGreaterElements(vector<int>& nums) {
        std::stack<int> st; // 记录元素对应的下标,不记录元素
        std::vector<int> ans(nums.size());

        int n=static_cast<int>(nums.size());

        for(int i=2*n-1;i>=0;--i)
        {
            while(!st.empty() && nums[i%n]>=nums[st.top()])
            {
                st.pop();
            }

            ans[i%n]=st.empty()?-1:nums[st.top()];

            st.push(i%n);
        }

        return ans;
    }
*/

// 移掉 K 位数字
/*
class Solution {
public:
    string removeKdigits(string num, int k) {

        // 单调栈
        std::stack<char> st;
        // 使得剩下的数字最小，需要保证靠前的数字尽可能小
        for(int i=0;i<static_cast<int>(num.size());++i)
        {
            while(k>0 && !st.empty() && num[i]<st.top())
            {
                --k;
                st.pop();
            }

            st.push(num[i]);
        }

        // 保证去除k位
        while(k--)
        {
            st.pop();
        }

        // 数字逆序保存在ans中
        std::string ans;
        while(!st.empty())
        {
            ans.push_back(st.top());
            st.pop();
        }

        // 去除前导零
        while(!ans.empty() && ans.back()=='0')
        {
            ans.pop_back();
        }

        // 逆置
        std::reverse(ans.begin(),ans.end());

        return ans.empty()?"0":ans;
    }
};
*/

// 去除重复字母
// 贪心加单调栈
/*
class Solution {
public:
    string removeDuplicateLetters(string s) {

        std::vector<int> count(26,0);
        std::vector<bool> visited(26,false);

        // 统计字符对应的个数
        for(auto ch:s)
        {
            count[ch-'a']++;
        }

        std::string ans;

        for(auto ch:s)
        {
            // 添加没有出现的字符
            if(!visited[ch-'a'])
            {
                // 当前字符小于栈顶字符
                while(!ans.empty() && ch<ans.back())
                {
                    // 如果对应的栈顶字符还有重复的则出栈
                    if(count[ans.back()-'a']>0)
                    {
                        // 先标记该栈顶字符没有访问过
                        visited[ans.back()-'a']=false;
                        ans.pop_back();
                    }
                    else // 如果没有重复的栈顶字符则无需出栈
                    {
                        break;
                    }
                }
                // 将该没有出现的字符入栈
                ans.push_back(ch);
                // 并且标记访问过
                visited[ch-'a']=true;
            }
            // 字符数量减一
            count[ch-'a']--;
        }

        return ans;
    }
};
*/

// 模拟栈
/*
// 输入
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty
// 输出
5
5
YES
4
NO
*/

/*
#include <iostream>
#include <string>

using namespace std;

const int N=1e6+10;

int st[N];

int tt=0;

int m=0;

int main()
{
    cin>>m;
    std::string op;
    while(m--)
    {
        cin>>op;

        if(op=="push")
        {
            int x;
            cin>>x;
            st[++tt]=x;
        }
        else if(op=="pop")
        {
            tt--;
        }
        else if(op=="empty")
        {
            if(tt==0)
            {
                std::cout<<"YES"<<std::endl;
            }
            else
            {
                std::cout<<"NO"<<std::endl;
            }
        }
        else
        {
            std::cout<<st[tt]<<std::endl;
        }

    }

    return 0;
}
*/

// 给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出−1
/*
#include <iostream>
#include <vector>
using namespace std;

const int N=1e6+10;

int st[N];
int tt=0;

int a[N];
int n=0;

int main()
{
    cin>>n;

    std::vector<int> ans;

    for(int i=0;i<n;++i) cin>>a[i];

    for(int i=0;i<n;++i)
    {
        while(tt && st[tt]>=a[i])
        {
            tt--;
        }

        if(tt==0)
        {
            ans.push_back(-1);
        }
        else
        {
            ans.push_back(st[tt]);
        }

        st[++tt]=a[i];
    }

    for(auto e:ans)
    {
        std::cout<<e<<" ";
    }

    return 0;
}
*/